package com.breeze.leetcode.zjtd.kotilin

class MaxDistanceOfTree {
    companion object {
        /**
         *  1. 情况1：左子树高度+右子树高度+1
         *  2. 情况2：Math.max(左子树最大距离,右子树最大距离)
         *  树的最大距离 = Math.max(情况1,情况2)
         */
        fun getMaxDistance(head: Node?): Int {
            var depth = arrayOfNulls<Int>(1)
            return process(head, depth)
        }

        private fun process(head: Node?, depth: Array<Int?>): Int {
            if (head == null) {
                depth[0] = 0
                return 0
            }
            // 左子树最大距离和最大高度
            var leftMaxDistance = process(head.left, depth)
            var leftDepth = depth[0]!!
            // 右子树最大距离和最大高度
            var rightMaxDistance = process(head.right, depth)
            var rightDepth = depth[0]!!
            // 当前树的高度
            depth[0] = Math.max(leftDepth, rightDepth) + 1

            var sit1 = leftDepth + rightDepth + 1
            var sit2 = Math.max(leftMaxDistance, rightMaxDistance)
            return Math.max(sit1, sit2)
        }
    }
}

class Node(var value: Int) {
    var left: Node? = null
    var right: Node? = null
}

fun main() {
    var head = Node(1)
    head.left = Node(2)
    head.right = Node(3)
    head.left?.left = Node(4)
    head.left?.right = Node(5)
    head.right?.left = Node(6)
    head.right?.right = Node(7)
    println(MaxDistanceOfTree.getMaxDistance(head))
}